package io.github.handyang.algorithms.graph;

public class DFSCC implements CC {
    private final Graph graph;
    private final boolean[] marked;
    private final int[] ids;
    private int count;

    public DFSCC(Graph graph) {
        this.graph = graph;

        this.marked = new boolean[this.graph.V()];
        this.ids = new int[this.graph.V()];

        for (int i = 0; i < marked.length; i++) {
            if (marked[i]) continue;

            dfs(i, count++);
        }
    }

    private void dfs(int start, int id) {
        marked[start] = true;
        ids[start] = id;

        for (Integer point : graph.adj(start)) {
            if (marked[point]) continue;

            marked[point] = true;
            ids[point] = id;

            dfs(point, id);
        }
    }

    @Override
    public boolean connected(int v, int w) {
        return ids[v] == ids[w];
    }

    @Override
    public int count() {
        return count;
    }

    @Override
    public int id(int v) {
        return ids[v];
    }
}
